package com.codingvip.link;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 链表是否存在环
 */
public class CheckListLoop {

        public static void main(String[] args) {
            ListNode listNode = init();

//            ListNode checkLoop = detectCycle(listNode);
            ListNode checkLoop = detectCycleBySet(listNode);

            System.out.println(checkLoop == null ? "无环" : checkLoop.val);
        }

    /**
     * 通过Set 检测环
     * @param head
     * @return
     */
    public static ListNode detectCycleBySet(ListNode head) {
            Set<ListNode> visited = new HashSet<ListNode>();

            ListNode node = head;
            while (node != null) {
                if (visited.contains(node)) {
                    return node;
                }
                visited.add(node);
                node = node.next;
            }

            return null;
        }

        public static ListNode isLinkedListContainsLoop(ListNode head) {
            if (head == null) {
                return null;
            }
            ListNode slowPtr = head;
            ListNode fastPtr = head;
            boolean isLoop = false;
            while (fastPtr.next != null && fastPtr.next.next != null) {
                slowPtr = slowPtr.next;
                fastPtr = fastPtr.next.next;
                if (slowPtr == fastPtr) {
                    isLoop = true;
                    break;
                }
            }
            if (isLoop) {
                slowPtr = head;
                while ((slowPtr = slowPtr.next) != (fastPtr = fastPtr.next)) {
                }
                return slowPtr;
            }


            return null;
        }

        /**
         * LEECODE
         */

        public static  ListNode detectCycle(ListNode head) {
            if (head == null) {
                return null;
            }
            ListNode slow = head;
            ListNode fast = head;
            boolean isLoop = false;
            while (fast.next != null && fast.next.next != null) {
                fast = fast.next.next;
                slow = slow.next;
                if (fast == slow) {
                    if (head ==slow) {
                        return head;
                    }
                    isLoop = true;
                    break;
                }
            }
            if (isLoop) {
                slow = head;
                while ((slow = slow.next) != (fast = fast.next)) {
                }
                return slow;
            }

            return null;
        }


        static ListNode init() {
            ListNode head = new ListNode(1);
            ListNode o2 = new ListNode(2);
            ListNode o3 = new ListNode(3);
            ListNode o4 = new ListNode(4);
            ListNode o5 = new ListNode(5);
            ListNode o6 = new ListNode(6);
            ListNode o7 = new ListNode(7);
            head.next = o2;
            o2.next = head;
//            o3.next = o2;
    //        o4.next = o5;
    //        o5.next = o6;
    //        o6.next = o7;
    //        o7.next = o3;
            return head;
        }

}
